package me.shan.sort;

import java.util.Arrays;

public class QuickSort {

    public static void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        swap(array, left + (int) (Math.random() * (right - left)), right);
        int[] temp = deal(array, left, right);
        quickSort(array, left, temp[0] - 1);
        quickSort(array, temp[1] + 1, right);
    }

    private static int[] deal(int[] array, int left, int right) {
        if (left > right) {
            return new int[]{-1, -1};
        }
        if (left == right) {
            return new int[]{left, right};
        }
        int less = left - 1, more = right, index = left;
        while (index < more) {
            if (array[index] == array[right]) {
                index++;
            } else if (array[index] < array[right]) {
                swap(array, ++less, index++);
            } else {
                swap(array, index, --more);
            }
        }
        swap(array, right, more);
        return new int[]{less + 1, more};
    }

    private static void swap(int[] array, int a, int b) {
        if (a == b) {
            return;
        }
        array[a] = array[a] ^ array[b];
        array[b] = array[a] ^ array[b];
        array[a] = array[a] ^ array[b];
    }

    public static void main(String[] args) {
        int[] array = {2, 4, 6, 1, 3, 5, 7, 3, 2, 8, 9, 1, 7, 3, 6, 0, 5, 2};
        int[] temp = new int[array.length];
        System.arraycopy(array, 0, temp, 0, temp.length);
        sort(array);
        System.out.println(Arrays.toString(array));
        Arrays.sort(temp);
        System.out.println(Arrays.toString(temp));
    }
}
